#coding: utf-8
import Properties
from Constants import *

from Util import *
from Graphics import *
import math

class Curve():	
	'''
		Classe reconhece os pontos tracados pelo usuario na tela e os armazena em forma de pontos.
		A origem se situa no canto superior esquerdo. O valor de y cresce de cima para baixo.
	'''
	
	#Constantes relativas a frequ�ncia dos pontos
	
	ALWAYS = 0
	ALMOST_ALWAYS = 2
	VERY_FREQUENTLY = 5
	FREQUENTLY = 8	#A cada 8 pontos reconhecidos, 1 ser� desenhado
	SOMETIMES = 12
	A_LITTLE = 16
	RARELY = 20
	ALMOST_NEVER = 30
	
	
	def __init__(self,size):
		self.pontos = []
		
		self.min_y_index,self.min_y_value = None,INF
		
		self._size_x = size[0]
		self._size_y = size[1]
		
		self._freq = Curve.FREQUENTLY
		self._flag_freq = self._freq
		
	def add_rect(self,p1,p2,manual=False):
		'''
			A curva e desenhada a partir de retas definidas pela posicao do mouse. Dessa forma, e preciso saber
			todos os pontos contidos nessa reta (lembrando que estamos em um universo discreto, os pontos devem
			ser discretizados - rasterizados - adequadamente )
		'''
		if manual == True: #Entao os pontos p1 e p2 que passo j� s�o pontos pr�-definidos		
			self.add_point( p1,True )
			return
			
		if  p1[0] >= self._size_x or p1[1] >= self._size_y or p2[0] >= self._size_x or p2[1] >= self._size_y:
			return
		
		deltax = p2[0] - p1[0]
		deltay = p2[1] - p1[1]

		if deltax >= 0:
			signx = 1
		else:
			signx = -1
			
		if deltay >= 0:
			signy = 1
		else:
			signy = -1
			
		deltax = signx*deltax
		deltay = signy*deltay
		
	
		if deltax == 0:
			self.tan_greater_one(p1[0],p1[1],deltax,deltay,signx,signy)
			return
		
		if (deltay/float(deltax)) <= 1:
			self.tan_smaller_one(p1[0],p1[1],deltax,deltay,signx,signy)
		else:
			self.tan_greater_one(p1[0],p1[1],deltax,deltay,signx,signy)
		

		
	def tan_smaller_one( self,x0,y0, dx, dy, sgnx, sgny ):
		d = 2*dy - dx
		
		if not self.exists( (x0,y0) ):
			self.add_point( (x0,y0) )
		
		for i in range(0,dx):
		
			if d > 0:
				d += 2*dy - 2*dx
				y0+= sgny*1
			else:
				d += 2*dy
				
			x0+= sgnx*1				
			
			if not self.exists( (x0,y0) ):
				self.add_point( (x0,y0) )

		
	def tan_greater_one( self, x0,y0, dx, dy, sgnx, sgny ):
		d = dy - 2*dx
		
		
		if not self.exists( (x0,y0) ):
			self.add_point( (x0,y0) )
		
		for i in range(0,dy):
		
			if d < 0:
				d += 2*dy - 2*dx
				x0+= sgnx*1
			else:
				d += -2*dx
			
			y0+= sgny*1			
			
			if not self.exists( (x0,y0) ):		
				self.add_point( (x0,y0) )
		
	def add_point(self,pt,manual=False):
		if manual==False:
			if self._flag_freq > 0:
				self._flag_freq-=1
				return
			else:
				self._flag_freq = self._freq				
				
		if self.min_y_value > pt[1]:
			self.min_y_value = pt[1]
			self.min_y_index = len(self.pontos)
			
		self.pontos.append( Point( pt[0],pt[1],len(self.pontos) ) )
				
	def exists(self,ponto):
		if len(self.pontos) == 0:
			return False
			
		pt_pair = self.pontos[ len(self.pontos)-1 ]
		pt_pair = ( pt_pair.x,pt_pair.y )
			
		if pt_pair != (ponto[0],ponto[1]):	
			return False
			
		return True
		
	def print_points(self):
		for p in self.pontos:
			print "(",p.x,",",p.y,")",",",
			
	def draw_curve(self,image):
		pi = self.pontos[0]
		p1 = pi
		for i in range(1,len(self.pontos) ):
			p2 = self.pontos[i]
			desenhar_reta_curva( (p1.x,p1.y),(p2.x,p2.y),image,(255,0,0))
			
			p1 = p2
			
		desenhar_reta_curva( (p2.x,p2.y),(pi.x,pi.y),image,(255,0,0))
		
		p1 = self.pontos[0]
		p2 = self.pontos[1]
		desenhar_reta_curva( (p1.x,p1.y),(p1.x,p1.y),image,(255,0,0),(255,0,0))
		desenhar_reta_curva( (p2.x,p2.y),(p2.x,p2.y),image,(255,0,0),(255,255,0))
				
class Snake():
	EPSON = 10e-4
	SIGMA = 10e-4
	INF = 0xEFEFEFEF
	
	def __init__(self,img,curva):		
		self.indexar_pontos(curva)

		self.comp_suavidade_flag = True
		self.comp_continuidade_flag = True
		self.comp_cor_flag = True
		
		self.xk = None
		self.max_iteracoes = 1500
				
		self.size = len(self.pontos)	
		self.img = img	
		
		self.debug = Debug()
		self.iteracao_atual = None
		self.inclui_debug = False
		
		self.historico = History()		
		
	def indexar_pontos(self,curva):
		self.pontos = []
		
		begin = curva.min_y_index
		len_curva = len(curva.pontos)
		
		if begin is None:
			return
			
		pt_zero = curva.pontos[begin]
		next = curva.pontos[ (begin+1)%len_curva ]
		
		if next.x > pt_zero.x:
			factor = 1
		else:
			factor = -1
		
		for i in range(0,len_curva):
			index = (begin+i*factor)%len_curva
			pt = curva.pontos[index]
			pt.index = i
			
			#pt.color = (255,0,( round(255/len_curva)*i) )
			
			self.pontos.append( pt )
		
	def go_to_historico(self,indice_relativo):
		self.xk = self.historico.get_history(indice_relativo)
		self.pontos = self.xk.points

	def go_back(self,indice_relativo):
		self.xk = self.historico.go_back(indice_relativo)
		self.pontos = self.xk.points

	def start(self):
		self.iteracao = 1
		
	def set_manual_alfa(self,index,coef):
		self.xk.points[index].manual_alfa = coef

	def set_manual_beta(self,index,coef):
		self.xk.points[index].manual_beta = coef
				
	def set_manual_gama(self,index,coef):
		self.xk.points[index].manual_gama = coef

	def set_manual_delta(self,index,coef):
		self.xk.points[index].manual_delta = coef						
		

	def minimizar(self):
		'''
			xk � o meu vetor de pontos na forma [ (x1,y1), (x2,y2) ... ] que ir� conter ao final das itera��es
			a solu��o do problema do contorno, sendo que, a princ�pio, seus valores s�o dados pelos pontos da 
			curva desenhados pelo usu�rios
			
			O m�todo que ser� usado para a minimiza��o da fun��o ser� o m�todo do gradiente. De acordo com este
			m�todo iremos fazer com que o conjunto solu��o caminhe para a resposta m�nima seguindo a dire��o inversa
			de seu gradiente ( o gradiente aponta para a dire��o de maior crescimento da fun��o )
		'''
		
		if self.xk is None:
			self.iteracao = 1
			self.xk = PointVector( self.pontos )	
			
			self.iteracao_atual = InfoIteration(self.iteracao)		
			self.ponto_medio = self.xk.update(self.cor,self.historico,self.iteracao_atual)
			
			
		#print self.xk
						
			
		if self.iteracao <= self.max_iteracoes:
			self.historico.add_to_history(self.xk)
									
			gradiente_f_xk = self.calcular_gradiente_f( self.xk )				
			normal_grad_f_xk = gradiente_f_xk.normal()

			'''
			if normal_grad_f_xk < 2:
				break
			'''
			
			self.dk = gradiente_f_xk.escalar_product(-1)			
			self.funcional = self.calcular_funcional(self.xk).normal() 
						
			self.lbda = self.busca_linear(self.xk,gradiente_f_xk,self.dk)
			self.xk = self.xk.sum_vector( self.dk.escalar_product(self.lbda),True )
			
			if self.inclui_debug:
				self.iteracao_atual.set_xk(self.xk)
				self.iteracao_atual.set_direcao(self.dk)
				self.iteracao_atual.set_funcional( self.funcional )	#Apenas para por no debug			
				self.iteracao_atual.set_lambda(self.lbda)
				self.debug.add_info(self.iteracao_atual)
				
				self.iteracao_atual = InfoIteration(self.iteracao+1)		
			
			self.iteracao+=1			
					
			
			self.ponto_medio = self.xk.update(self.cor,self.historico,self.iteracao_atual)		
			self.pontos = self.xk.points
	
	def busca_linear(self,xk,grad_f_xk,dk): 
		lbda = 1/(128.0)
		count = 0
		
		self.inclui_debug = False
		
		while(count < 7):

			condicao_armijo_pt_1 = ( self.calcular_funcional(xk) ).normal()
			condicao_armijo_pt_2 = ( grad_f_xk.dot_product( dk ) ) * ( Snake.SIGMA*lbda)
			
			condicao_armijo = condicao_armijo_pt_1 + condicao_armijo_pt_2
			
			''' Calculando a Normal do funcional - Armijo Normal
			if ( self.calcular_funcional( xk.somar_vetor( dk.multiplicar_escalar(lbda) ) ) ).normal() > condicao_armijo:
				lbda= lbda/2.0
			else:
				break				
			'''
			
			p1 = self.calcular_funcional( xk.sum_vector( dk.escalar_product(lbda) ) ).normal()
			#Somando as componentes do Funcional - Armijo inverso
			if p1 < condicao_armijo:
				lbda= lbda*2.0
			else:
				lbda = lbda/2.0	
				break
				
			count+=1
			
		self.inclui_debug = True
			
		return lbda
		
	def calcular_funcional( self,xk ):
		comp_cont_x = 0
		comp_suav_x = 0
		comp_cor_x = 0
		
		comp_cont_y = 0
		comp_suav_y = 0
		comp_cor_y = 0		
		
		for pt in xk.points:
			comp_cont_pt = self.calcular_comp_continuidade(pt,xk) 
			
			comp_cont_x+= comp_cont_pt[0]*pt.alfa
			comp_cont_y+= comp_cont_pt[1]*pt.alfa
			
			comp_suav_pt = self.calcular_comp_suavidade(pt,xk)
			
			comp_suav_x+= comp_suav_pt[0]*pt.beta
			comp_suav_y+= comp_suav_pt[1]*pt.beta
			
			comp_cor_pt = self.calcular_comp_cor(pt)
			
			comp_cor_x+= comp_cor_pt[0]*pt.gama[0]
			comp_cor_y+= comp_cor_pt[1]*pt.gama[1]
			
			pt.comp_continuidade = comp_cont_pt
			pt.comp_suavidade = comp_suav_pt
			pt.comp_cor = comp_cor_pt
			
			if self.inclui_debug:
				self.iteracao_atual.infos[pt.index].comp_continuidade = comp_cont_pt
				self.iteracao_atual.infos[pt.index].comp_suavidade = comp_suav_pt
				self.iteracao_atual.infos[pt.index].comp_cor = comp_cor_pt
			

			self.comp_continuidade = (comp_cont_x,comp_cont_y)
			self.comp_suavidade = (comp_suav_x,comp_suav_y)
			self.comp_cor = (comp_cor_x,comp_cor_y)

		x,y= 0,0
			
		if self.comp_continuidade_flag:
			x += comp_cont_x
			y += comp_cont_y
			
		if self.comp_suavidade_flag:
			x+= comp_suav_x
			y+= comp_suav_y
			
		if self.comp_cor_flag:
			x += -comp_cor_x
			y += -comp_cor_y
			
		
		
		result = PointVector()
		result.add_point( Point(x,y,0) )
		
		return result		
	
	def calcular_gradiente_f( self, xk ):
		derivada = PointVector()
		
		for p in xk.points:
			derivada.add_point( self.calcular_derivada_f( p,xk ) )
						
		return derivada
		
	def calcular_comp_continuidade(self,pt,xk):
		pt_1 = xk.points[pt.index-1]
		
		xi = pt.x
		xi_1 = pt_1.x
		
		yi = pt.y
		yi_1 = pt_1.y
	
		x = pow( (xi - xi_1 ), 2 )	
		y = pow( (yi - yi_1 ), 2 )
		
		return (x,y)

	def calcular_comp_suavidade(self,pt,xk):
		pt_1 = xk.points[pt.index-1]
		pt_m1 = xk.points[pt.index+1]
		
		xi = pt.x
		xi_1 = pt_1.x
		xi_m1 = pt_m1.x
		
		yi = pt.y
		yi_1 = pt_1.y
		yi_m1 = pt_m1.y
				
		x =	pow( (xi_m1 -2*xi + xi_1 ), 2 )
		y =	pow( (yi_m1 -2*yi + yi_1 ), 2 )
		
		return (x,y)
		
	def calcular_comp_cor(self,pt):	
		x =	pow( (self.cor(pt.x,pt.y) - self.cor(pt.x-1,pt.y) ), 2 )
		y =	pow( (self.cor(pt.x,pt.y) - self.cor(pt.x,pt.y-1) ), 2 )			
		
		return (x,y)
	
	def calcular_derivada_comp_continuidade(self,pt,xk):				
		pt_1 = xk.points[pt.index-1]
		pt_m1 = xk.points[pt.index+1]
		
		xi = pt.x
		xi_1 = pt_1.x
		xi_m1 = pt_m1.x
		
		yi = pt.y
		yi_1 = pt_1.y
		yi_m1 = pt_m1.y
		
		comp_cont_x = 4*xi - 2*xi_1 - 2*xi_m1
		comp_cont_y = 4*yi - 2*yi_1 - 2*yi_m1
		
		return ( comp_cont_x,comp_cont_y )
		
	def calcular_derivada_comp_suavidade(self,pt,xk):
		pt_1 = xk.points[pt.index-1]
		pt_2 = xk.points[pt.index-2]
		pt_m1 = xk.points[pt.index+1]
		pt_m2 = xk.points[pt.index+2]
		
		xi = pt.x
		xi_1 = pt_1.x
		xi_2 = pt_2.x
		xi_m1 = pt_m1.x
		xi_m2 = pt_m2.x
		
		yi = pt.y
		yi_1 = pt_1.y
		yi_2 = pt_2.y
		yi_m1 = pt_m1.y
		yi_m2 = pt_m2.y
		
		comp_suav_x = -8*xi_m1 - 8*xi_1 + 12*xi + 2*xi_m2 + 2*xi_2
		comp_suav_y = -8*yi_m1 - 8*yi_1 + 12*yi + 2*yi_m2 + 2*yi_2
			

		return (comp_suav_x, comp_suav_y )
		
	def calcular_derivada_comp_cor(self,pt,xk):
		pt_1 = xk.points[pt.index-1]
		pt_2 = xk.points[pt.index-2]
		pt_m1 = xk.points[pt.index+1]
		pt_m2 = xk.points[pt.index+2]
		
		xi = pt.x
		xi_1 = pt_1.x
		xi_2 = pt_2.x
		xi_m1 = pt_m1.x
		xi_m2 = pt_m2.x
		
		yi = pt.y
		yi_1 = pt_1.y
		yi_2 = pt_2.y
		yi_m1 = pt_m1.y
		yi_m2 = pt_m2.y
		
		comp_cor_x = -2*( self.cor(xi,yi) - self.cor(xi-1,yi) ) * ( ( self.cor(xi,yi) - self.cor(xi-1,yi) ) - ( self.cor(xi-1,yi) - self.cor(xi-2,yi) ) )						
		comp_cor_y = -2*( self.cor(xi,yi) - self.cor(xi,yi-1) ) * ( ( self.cor(xi,yi) - self.cor(xi,yi-1) ) - ( self.cor(xi,yi-1) - self.cor(xi,yi-2) ) )
	
		
		return (comp_cor_x,comp_cor_y)
		
		
	def calcular_derivada_f( self, pt, xk ):				
		'''
		comp_suav_cont_x = 16*xi - 10*xi_1 - 10*xi_m1 + 2*xi_m2 + 2*xi_2
		comp_suav_cont_y = 16*yi - 10*yi_1 - 10*yi_m1 + 2*yi_m2 + 2*yi_2 
		'''
		
		x,y=0,0
		
		comp_cont = (0,0)
		comp_suav = (0,0)
		comp_cor = (0,0)
			
		if self.comp_continuidade_flag:
			comp_cont = self.calcular_derivada_comp_continuidade(pt,xk)
			x += comp_cont[0]*pt.alfa
			y += comp_cont[1]*pt.alfa
			
			
		if self.comp_suavidade_flag:
			comp_suav = self.calcular_derivada_comp_suavidade(pt,xk)
			x += comp_suav[0]*pt.beta
			y += comp_suav[1]*pt.beta		
			
					
		if self.comp_cor_flag:
			comp_cor = self.calcular_derivada_comp_cor(pt,xk)
			
			x += comp_cor[0]*pt.gama[0]
			y += comp_cor[1]*pt.gama[1]		

		if self.inclui_debug:
			self.iteracao_atual.infos[pt.index].grad_comp_continuidade = comp_cont
			self.iteracao_atual.infos[pt.index].grad_comp_suavidade = comp_suav		
			self.iteracao_atual.infos[pt.index].grad_comp_cor = comp_cor		

		pt.grad_comp_continuidade = comp_cont
		pt.grad_comp_suavidade = comp_suav
		pt.grad_comp_cor = comp_cor
			
			
		#Direcao linear esta dissociado da influencia do lbda
		if self.iteracao > 10:			 
			x += pt.dir_pt_linear.x*pt.delta*-1
			y += pt.dir_pt_linear.y*pt.delta*-1
								
		novo_ponto = Point( x, y,pt.index )
					
		return novo_ponto

		
	def cor(self,x,y):
		try:	
			return self.img.getpixel( ( int( round(x) ), int( round(y) ) ) )* COLOR_NORMALIZER
		except:
			return 0
			
				